#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <xmmintrin.h> //SSE
#include <emmintrin.h> //SSE2
#include <pmmintrin.h> //SSE3
#include <tmmintrin.h> //SSSE3
#include <smmintrin.h> //SSE4.1
#include <nmmintrin.h> //SSSE4.2
#include <stdlib.h>
#include <iostream>
#include <ctime>

using namespace std;

void special_sse(int row, int col, int* now, int** matrix)
{
    int i, j, k;
    for (i = 0; i < row; i++)
    {
        int bpos = i / 32, spos = i % 32;
        if (now[bpos] >> (31 - spos) != 0)
        {
            if (matrix[row - 1 - i][bpos] >> (31 - spos) == 0)
            {
                for (j = 0; j <= col - 4; j += 4)
                {
                    __m128i temp = _mm_loadu_si128((__m128i*)(now + j));
                    _mm_storeu_si128((__m128i*)(matrix[row - 1 - i] + j), temp);
                }
                for (; j < col; j++)
                    matrix[row - 1 - i][j] = now[j];
                return;
            }
            else
            {
                for (j = 0; j <= col - 4; j += 4)
                {
                    __m128i t1 = _mm_loadu_si128((__m128i*)(matrix[row - 1 - i] + j));
                    __m128i t2 = _mm_loadu_si128((__m128i*)(now + j));
                    t2 = _mm_xor_si128(t1, t2);
                    _mm_storeu_si128((__m128i*)(now + j), t2);
                }
                for (; j < col; j++)
                    now[j] ^= matrix[row - 1 - i][j];
            }
        }
    }
}

void special(int row, int col, int* now, int** matrix)
{
    int i, j;
    for (i = 0; i < row; i++)
    {
        int bpos = i / 32, spos = i % 32;
        if (now[bpos] >> (31 - spos) != 0)
        {
            if (matrix[row - 1 - i][bpos] >> (31 - spos) == 0)
            {
                for (j = 0; j < col; j++)
                    matrix[row - 1 - i][j] = now[j];
                return;
            }
            else
            {
                for (j = 0; j < col; j++)
                    now[j] ^= matrix[row - 1 - i][j];
            }
        }
    }
}

int init_matrix(int* a, int row, int m)
{
    for (int j = 0; j < m; j++) a[j] = 0;
    int q = (rand() % row) / 2;
    while (q == 0) q = (rand() % row) / 2;
    int p = row;
    int temp;
    for (int i = 0; i < q; i++)
    {
        if (p != 0)
        {
            p = rand() % p;
            if (i == 0)
                temp = p;
        }
        int bpos = p / 32, spos = p % 32;
        bpos = m - 1 - bpos;
        int ans = 1;
        ans = ans << spos;
        a[bpos] |= ans;
    }
    return temp;
}

int main()
{
    int row, m, u, l;
    srand(time(0));
    row = 20;
    while (row <= 10000)
    {
        u = rand() % (row / 2);
        while (u == 0) u = rand() % (row / 2);
        l = rand() % row + row / 2;
        if (row % 32 == 0)
            m = row / 32;
        else
            m = row / 32 + 1;
        int** mc = new int* [row];
        int** mb = new int* [row];
        for (int i = 0; i < row; i++)
        {
            mc[i] = new int[m];
            mb[i] = new int[m];
        }
        for (int i = 0; i < row; i++)
            for (int j = 0; j < m; j++)
            {
                mc[i][j] = 0;
                mb[i][j] = 0;
            }
        for (int i = 0; i < u; i++)
        {
            int* a1 = new int[m];
            int* a2 = new int[m];
            int temp = init_matrix(a1, row, m);
            for (int j = 0; j < m; j++)
                a2[j] = a1[j];
            for (int j = 0; j < m; j++)
            {
                mc[row - 1 - temp][j] = a1[j];
                mb[row - 1 - temp][j] = a2[j];
            }
        }

        struct timeval tstart, tend;
        double timeUsed1 = 0.0, timeUsed2 = 0.0;

        for (int i = 0; i < l; i++)
        {
            int* a1 = new int[m];
            int* a2 = new int[m];
            int temp = init_matrix(a1, row, m);
            for (int j = 0; j < m; j++)
                a2[j] = a1[j];

            gettimeofday(&tstart, NULL);
            special(row, m, a1, mc);
            gettimeofday(&tend, NULL);
            timeUsed1 += 1000000 * (tend.tv_sec - tstart.tv_sec) + tend.tv_usec - tstart.tv_usec;

            gettimeofday(&tstart, NULL);
            special_sse(row, m, a2, mb);
            gettimeofday(&tend, NULL);
            timeUsed2 += 1000000 * (tend.tv_sec - tstart.tv_sec) + tend.tv_usec - tstart.tv_usec;
        }
        cout << row << " " << timeUsed1 / timeUsed2 * 100 << "%" << endl;

        if (row >= 3000) row += 1000;
        if (row >= 1000 && row < 3000) row += 500;
        if (row >= 500 && row < 1000) row += 100;
        if (row >= 200 && row < 500) row += 50;
        if (row >= 100 && row < 200) row += 20;
        if (row < 100) row += 10;
    }
    return 0;
}
